package com.zyk.grate_offer.class06;

/**
 * @author zhangsan
 * @date 2021/5/12 10:32
 */
public class Code03_MaximumXorWithAnElementFromArray {


    // nums: 数组
    // queries[0]: 和这个数异或,  queries[1]: 原数组的值不能超过它
    // 每一个数据都要保证最大,和queries[0]异或, 不能和超过queries[1]的数异或. 的异或结果最大值. 没有为-1
    public static int[] maximizeXor(int[] nums, int[][] queries) {
        NumTrie tree = new NumTrie();
        for (int num : nums) {
            tree.addNumber(num);
        }
        int N = queries.length;
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            int num = queries[i][0];
            int target = queries[i][1];
            res[i] = tree.maxXor(num, target);
        }
        return res;
    }


    // 题目保证, 都是正数
    public static class NumTrie {

        Node head = new Node();

        public void addNumber(int num) {
            int path;
            Node cur = head;
            for (int i = 30; i >= 0; i--) {
                path = (num >> i) & 1;
                if (cur.nexts[path] == null)
                    cur.nexts[path] = new Node();
                cur.min = Math.min(cur.min, num);
                cur = cur.nexts[path];
            }
            cur.min = Math.min(cur.min, num);
        }

        public int maxXor(int num, int target) {
            if (head.min > target) return -1;
            int path, best, res = 0;
            Node cur = head;
            for (int i = 30; i >= 0; i--) {
                path = (num >> i) & 1;
                best = (path ^ 1);          // 期待的最大的路
                best = (cur.nexts[best] == null || cur.nexts[best].min > target) ? path : best;     // 如果那条路不存在或者那条路上的最小值比target都要大, 就不能走那条路
                res |= (path ^ best) << i;
                cur = cur.nexts[best];
            }
            return res;
        }

        public static class Node {
            Node[] nexts = new Node[2];
            int min = Integer.MAX_VALUE;
        }
    }

}
